#include<stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BiTNode {
    ElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
} BiTNode, *BiTree;

//辅助队列
typedef struct Squeue {
    BiTree addr;
    struct Squeue *next;
} Squeue, *pSqueue;

//前序遍历
void PreOrder(BiTree T) {
    if (T != NULL) {
        putchar(T->c);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
int main() {
    BiTree tree = NULL;
    BiTree pnew;
    ElemType c;
    pSqueue phead = NULL, ptail = NULL, pcur = NULL, list_pnew = NULL;
    while (scanf("%c", &c)) {
        if (c == '\n') {
            break;
        }
        //为树申请节点
        pnew = (BiTree) calloc(1, sizeof(BiTNode));
        pnew->c = c;
        //为辅助队列申请空间
        list_pnew = (pSqueue) calloc(1, sizeof(Squeue));
        //队列放入申请的结点
        list_pnew->addr = pnew;

        if (tree == NULL) {
            tree = pnew;
            phead = list_pnew;
            ptail = list_pnew;
            pcur = list_pnew;
        } else {
            //队列尾部元素入队
            ptail->next = list_pnew;
            ptail = list_pnew;
            if (pcur->addr->lchild == NULL) {
                pcur->addr->lchild = pnew;
            } else if (pcur->addr->rchild == NULL) {
                pcur->addr->rchild = pnew;
                pcur = pcur->next;
            }
        }
    }
    PreOrder(tree);
    return 0;
}